package leetcode.day_2020_2021_2_1_2021_2_7;

/**
 * 33. 搜索旋转排序数组
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
 * 输入：nums = [4,5,6,7,0,1,2], target = 0
 * 输出：4
 */
public class LeetCode0033 {

    public static int search(int[] nums, int target) {
        // 使用二分查找法
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = (left+right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] >= nums[left]) { // 先判断mid在左端还是右端
                if (target>=nums[left] && target<nums[mid]) {   // 再判断target在mid左端还是右端
                    right = mid-1;
                } else {
                    left = mid+1;
                }
            } else if (nums[mid] < nums[right]) {
                if (target<=nums[right] && target>nums[mid]) {
                    left = mid+1;
                } else {
                    right = mid-1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(search(new int[]{4,5,6,7,0,1,2}, 0));
        System.out.println(search(new int[]{4,5,6,7,0,1,2}, 3));
    }
}
